from ListeChainee import *

class ListeChainee2(ListeChainee):
    """Improved version of ListeChainee (inheriting all its methods), solution to problem 4 from exam_jun12.pdf"""
    def __init__(self, *args):
        ListeChainee.__init__(self, *args)
    def permutation_it(self):
        """
        Iterative version of permutation(), just for fun.
        >>> x = ListeChainee2(1, 2, 3, 4, 5, 6)
        >>> x.permutation_it()
        >>> print x
        [2, 1, 4, 3, 6, 5]
        >>> x = ListeChainee2(1, 2, 3, 4)
        >>> x.permutation_it()
        >>> print x
        [2, 1, 4, 3]
        >>> x = ListeChainee2(1, 2, 3)
        >>> x.permutation_it()
        >>> print x
        [2, 1, 3]
        >>> x = ListeChainee2()
        >>> x.permutation_it()
        >>> print x
        []
        """
        #first two nodes
        p = self.head
        if p is None: return #nothing to do
        x = p.next
        if x is None: return #nothing to do
        #new order: hd,p,x,nx -> hd,x,p,nx
        p.next = x.next
        x.next = p
        self.head = x
        #now, swap two nodes after p and make p point 
        #to the new 2nd node... loop 'til the end.
        while 1:
            #get a couple of consecutive nodes after p
            #if we can't, we're done.
            x = p.next
            if x is None: return
            y = x.next
            if y is None: return
            #new order: p,x,y,nx -> p,y,x,nx
            x.next = y.next
            y.next = x
            p.next = y
            #loop...
            p = x
    def permutation(self, nd=None):
        """
        >>> x = ListeChainee2(1, 2, 3, 4, 5, 6)
        >>> x.permutation()
        >>> print x
        [2, 1, 4, 3, 6, 5]
        >>> x = ListeChainee2(1, 2, 3, 4)
        >>> x.permutation()
        >>> print x
        [2, 1, 4, 3]
        >>> x = ListeChainee2(1, 2, 3)
        >>> x.permutation()
        >>> print x
        [2, 1, 3]
        >>> x = ListeChainee2()
        >>> x.permutation()
        >>> print x
        []
        """
        if nd is None:
            #first call
            #this "if" is needed to avoid infinite recursion: as self.head is None,
            #this function will be called over and over, until the stack eventually explodes.
            if not self.head is None:
                self.head = self.permutation(self.head)
            #else, there's nothing to do (nor to return).
        else:
            #internal call... we'll return the new next node
            p1 = nd
            p2 = nd.next
            if p2==None:
                return nd #only one element, nothing to do
            else:
                #old order: p1 p2 nx
                p1.next = p2.next
                p2.next = p1
                #new order: p2 p1 nx
                if not p1.next is None: #any nx? avoid infinite recursion (same reason as in "first call")
                    p1.next = self.permutation(p1.next)
                return p2 #pointer to the new first node...


if __name__=="__main__":
    import doctest
    doctest.testmod()
